I. Field of the Invention
The invention relates generally to the field of digital data processing systems, and more specifically to processors for use in such systems. The invention finds particular usefulness in processors which "prefetch", that is, which fetch instructions in an instruction stream while they are in the process of executing an instruction, the prefectched instruction being executed after the instruction being executed. The invention enables the processor to determine if an instruction is a conditional branch instruction, in which a determination is made as to whether a branch in an instruction stream should or should not be taken depending on the results of prior processing, and to prefetch both the instructions in the "branch taken" instruction stream as well as from the "branch not taken" instruction stream.
II. Description of the Prior Art
A digital data processing system generally includes three basic elements; namely, a memory element, an input/output element, and a processor element, all interconnected by one or more busses. The memory element stores data in addressable storage locations. This data includes both operands and instructions for processing the operands. The processor element causes data to be transferred or fetched, to it from the memory element, interprets the incoming data as either instructions or operands, and processes the operands in accordance with the instruction. The results are then stored in addressed locations in the memory element. An input/output element also communicates with the memory element in order to transfer data into the system and to obtain the processed data from it. The input/output elements normally operate in accordance with control information supplied to it by the processor element. The input/output elements may include, for example, printers, teletypewriters or keyboards and video display terminals, and may also include secondary data storage devices such as disk drives or tape drives.
Typically, a processor retrieves instructions in a stream from the memory element. The processor unit maintains a program counter which contains the address of the instruction being processed. After a current instruction is retrieved, the program counter can be incremented to contain the address of the location in memory which contains the next instruction in the instruction stream.
U.S. Pat. No. 4,236,206, issued to William D. Strecker, et al, on Nov. 25, 1980, discloses an improvement in which a single instruction may take a variable number of storage locations in the memory element. The central processor unit includes an instruction buffer into which retrieved words from the instruction stream are loaded. Generally, as the processor processes the portions of the instruction in the instruction buffer, they are shifted out and succeeding words are shifted up in the buffer. The processor prefetches instruction words in the instruction stream to keep the instruction buffer filled. When the processor finishes processing a current instruction, the prefetched words of the next instruction shift up in the buffer and are immediately available to the processor for processing after it has finished processing the current instruction. This prefetch enables the processor to process instructions more quickly.
A problem arises, however, if a branch instruction is encountered, which may require the processor to either continue processing instructions from the current stream or shift to another instruction stream. Some branches are unconditional.
Other branches are conditional, and the processor determines whether or not to shift to the alternate instruction stream depending on the state of the processor when the instruction is encountered. The processor, when it encounters an unconditional branch, can begin prefetching from the "branch taken" instruction stream immediately. However, a conditional branch presents the processor with a dilemma. It may continue prefetching from the current instruction stream, in which case if the branch is taken, the prefetched instructions will not be used. Contrariwise, it may prefetch instructions from the "branch taken" instruction stream, but if the branch is not taken then those instruction words will not be used. A third alternative is to disable instruction prefetching in response to a conditional branch instruction. All three alternatives can delay instruction processing at least sometimes.